package me.mingshan.leetcode;

import java.util.Stack;

/**
 * https://leetcode.cn/problems/maximum-twin-sum-of-a-linked-list/
 * <p>
 * 在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
 * <p>
 * 比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
 * 孪生和 定义为一个节点和它孪生节点两者值之和。
 * <p>
 * 给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
 *
 *
 * 输入：head = [5,4,2,1] 输出：6
 * 解释： 节点 0 和节点 1 分别是节点 3 和 2 的孪生节点。孪生和都为 6 。 链表中没有其他孪生节点。 所以，链表的最大孪生和是 6 。
 *
 * @author hanjuntao
 * @date 2025/8/6 0006
 */
public class L_2130_链表最大孪生和 {

    public static void main(String[] args) {
        ListNode node1 = new ListNode(5);
        ListNode node2 = new ListNode(4);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(1);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;

        System.out.println(pairSum2(node1));
    }

    /**
     * 暴力解法
     *
     * 思路：
     * 1. 获取链表的长度
     * 2. 在遍历每个节点时，获取该节点的孪生节点
     * 3. 获取孪生节点的值，并计算孪生和，并更新最大孪生和
     * 4. 返回最大孪生和
     *
     * 该算法最大的问题是在找到孪生节点的复杂度
     * 从孪生数的定义可知，首尾互为孪生数
     *
     * 时间复杂度：O(n^2)
     *
     * @param head
     * @return
     */
    public static int pairSum(ListNode head) {
        int result = 0;

        int count = 0;
        ListNode curr = head;
        while (curr != null) {
            curr = curr.next;
            count++;
        }

        int end = (count) / 2 - 1;

        curr = head;
        int index = 0;
        while (curr != null) {
            if (index <= end) {
                ListNode pair = findPair(head,  count, index);
                result = Math.max(result, curr.val + pair.val);
            }

            curr = curr.next;
            index++;
        }

        return result;
    }

    private static ListNode findPair(ListNode head, int count, int index) {

        ListNode curr = head;
        int cindex = 0;
        while (curr != null) {
            if (cindex == count - 1 - index) {
                return curr;
            }
            curr = curr.next;
            cindex++;
        }

        return null;
    }

    /**
     * 从题意可知，孪生数就是首尾对称的数
     *
     * 可以先找到中点，然后将中点前面的入栈
     * 然后遍历中点及以后的节点，同时弹出栈的元素，此时两个元素为孪生数
     * 然后更新最大值
     *
     * @param head
     * @return
     */
    public static int pairSum2(ListNode head) {
        int result = 0;

        int count = 0;
        ListNode curr = head;
        while (curr != null) {
            count++;
            curr = curr.next;
        }

        int mid =  count / 2 + 1;

        count = 0;
        curr = head;
        Stack<Integer> stack = new Stack<>();
        while (curr != null) {
            count++;

            if (count < mid) {
                stack.push(curr.val);
            } else {
                Integer pop = stack.pop();
                result = Math.max(result, curr.val + pop);
            }

            curr = curr.next;
        }

        return result;
    }

}
